%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 1: Distancia de Hamming %
% distHam(+S, ?T, ?D)               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

distHam([], [], 0).
distHam([S|Ss], [T|Ts], NN) :-
	ground([T|Ts]),
	esCadena([S|Ss]),
	esCadena([T|Ts]),
	length([S|Ss], L1),
	length([T|Ts], L2),
	L1 == L2,
	distHam(Ss,Ts,N),
	abs(S-T, Delta),
	NN is N + Delta.

distHam(S, T, NN) :-
	not(ground(T)),
	esCadena(S),	 
 	length(S,LS), armaLista(LS,[], L), T = L,
 	distHam(S,L,NN).

entre(X,Y,X) :- X =< Y.
entre(X,Y,Z) :- X < Y, N is X+1, entre(N,Y,Z).

armaLista(0,[],[]).
armaLista(N,L,L) :- N>0, length(L,Z), Z == N.
armaLista(N,L,R) :- N>0, length(L,Z), Z < N,
	entre(0,1,E), append([E],L, LL), armaLista(N, LL,R).

armaListaAt(0,X,X).
armaListaAt(N,L,L) :- N>0, length(L,Z), Z == N.
armaListaAt(N,L,R) :- N>0, length(L,Z), Z < N,
	entre(0,1,E), append(L,[E], LL), armaListaAt(N, LL,R).

% esCadena(+S)
esCadena([]).
esCadena([S|Ss]) :- memberchk(S, [0,1]), esCadena(Ss).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 2: Distancia de Prefijos %
% distPref(+S, ?T, ?D)		     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

distPref([],[],0).
distPref([],T,N) :- ground(T), esCadena(T), length(T,N), N > 0.
distPref(S,T,N) :- ground(T), T==[], esCadena(S), length(S,N), N > 0.
distPref([S|Ss], [T|Ts], N) :- ground([T|Ts]), esCadena([S|Ss]),
        esCadena([T|Ts]), T = S, distPref(Ss, Ts, N).
distPref([S|Ss], [T|Ts], N) :- ground([T|Ts]), esCadena([S|Ss]),
	esCadena([T|Ts]),
        T \= S,
	length(Ss,L1), 
	length(Ts,L2), 
	N is L1+L2+2.
distPref(S,T,N) :- not(ground(T)), ground(N), esCadena(S), length(S,LS),
        LT is LS+N, entre(0,LT,X), armaLista(X,[],LI),
         T = LI, distPref(S,LI,N).
distPref(S,T,N) :- not(is_list(T)), not(ground(N)), esCadena(S),
	desde(0,N), distPref(S,T,N).
distPref(S,T,N) :- is_list(T), not(ground(T)), not(ground(N)), esCadena(S),
	length(T, LT), length(S, LS), entre(0,LT+LS,N), distPref(S,T,N).
        
desde(X,X).
desde(X,Y) :- N is X+1, desde(N,Y).

prefijo(Lista, Pref) :- append(Pref, _, Lista).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 3: Distancia de edición %
% distEd(+S, ?T, ?D)                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

distEd([],[],0).
distEd([],T,N) :- ground(T), esCadena(T), length(T,N), N > 0.
distEd(S,T,N) :- ground(T), T == [], esCadena(S), length(S,N), N > 0.
distEd([S|Ss],[T|Ts],N) :- ground([T|Ts]),
	esCadena([S|Ss]),
	esCadena([T|Ts]),
	distEd(Ss,Ts,N1),
	distEd(Ss,[T|Ts],N2),
	distEd([S|Ss],Ts,N3),
	abs(S-T,D),
	NN1 is N1+D,
	NN2 is N2+1,
	NN3 is N3+1,
	min_list([NN1,NN2,NN3],N).
distEd(S,T,N) :- not(ground(T)), ground(N), esCadena(S), length(S,LS),
        LT is LS+N, entre(0,LT,X), armaLista(X,[],LI), 
        distEd(S,LI,N), T = LI.
distEd(S,T,N) :- not(is_list(T)), not(ground(N)), esCadena(S),
	desde(0,N), distEd(S,T,N).
distEd(S,T,N) :- is_list(T), not(ground(T)), not(ground(N)), esCadena(S),
	length(T, LT), length(S, LS), entre(0,LT+LS,N), distEd(S,T,N).


